{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Vacation Days"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxVacationDays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大休假天数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>力扣想让一个最优秀的员工在 <strong>N</strong> 个城市间旅行来收集算法问题。 但只工作不玩耍，聪明的孩子也会变傻，所以您可以在某些特定的城市和星期休假。您的工作就是安排旅行使得最大化你可以休假的天数，但是您需要遵守一些规则和限制。</p>\n",
    "\n",
    "<p><strong>规则和限制：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>您只能在 <strong>N</strong> 个城市之间旅行，用 <code>0</code> 到 <code>n-1</code> 的索引表示。一开始，您在索引为 <code>0</code> 的城市，并且那天是<strong>星期一</strong>。</li>\n",
    "\t<li>这些城市通过航班相连。这些航班用&nbsp;<code>n x n</code>&nbsp;矩阵<strong> flights</strong>（不一定是对称的）表示，<strong>flights[i][j] </strong>代表城市 <code>i</code> 到城市 <code>j</code> 的航空状态。如果没有城市 <code>i</code> 到城市 <code>j</code> 的航班，<code>flights[i][j] = 0</code>&nbsp;；否则，<code>flights[i][j] = 1</code>&nbsp;。同时，对于所有的 <code>i</code> ，<code>flights[i][i] = 0</code>&nbsp;<strong>。</strong></li>\n",
    "\t<li>您总共有 <code>k</code>&nbsp;周（<strong>每周7天</strong>）的时间旅行。您<strong>每天</strong>最多只能乘坐一次航班，并且只能在每周的<strong>星期一</strong>上午乘坐航班。由于飞行时间很短，我们不考虑飞行时间的影响。</li>\n",
    "\t<li>对于每个城市，不同的星期您休假天数是不同的，给定一个 <strong>N*K</strong> 矩阵 <strong>days</strong> 代表这种限制，<strong>days[i][j] </strong>代表您在第j个星期在城市i能休假的最长天数。</li>\n",
    "\t<li>如果您从 <code>A</code> 市飞往 <code>B</code> 市，并在当天休假，扣除的假期天数将计入 <code>B</code> 市当周的休假天数。</li>\n",
    "\t<li>我们不考虑飞行时数对休假天数计算的影响。</li>\n",
    "</ol>\n",
    "\n",
    "<p>给定 <code>flights</code> 矩阵和 <code>days</code> 矩阵，您需要输出 <code>k</code>&nbsp;周内可以休假的最长天数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]\n",
    "<strong>输出:</strong> 12\n",
    "<strong>解释:</strong> \n",
    "最好的策略之一：\n",
    "第一个星期 : 星期一从城市 0 飞到城市 1，玩 6 天，工作 1 天。 \n",
    "（虽然你是从城市 0 开始，但因为是星期一，我们也可以飞到其他城市。） \n",
    "第二个星期 : 星期一从城市 1 飞到城市 2，玩 3 天，工作 4 天。\n",
    "第三个星期 : 呆在城市 2，玩 3 天，工作 4 天。\n",
    "Ans = 6 + 3 + 3 = 12. \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> \n",
    "由于没有航班可以让您飞到其他城市，你必须在城市 0 呆整整 3 个星期。 \n",
    "对于每一个星期，你只有一天时间玩，剩下六天都要工作。 \n",
    "所以最大休假天数为 3.\n",
    "Ans = 1 + 1 + 1 = 3. \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]]\n",
    "<strong>输出:</strong> 21\n",
    "<strong>解释:</strong>\n",
    "最好的策略之一是：\n",
    "第一个星期 : 呆在城市 0，玩 7 天。 \n",
    "第二个星期 : 星期一从城市 0 飞到城市 1，玩 7 天。\n",
    "第三个星期 : 星期一从城市 1 飞到城市 2，玩 7 天。\n",
    "Ans = 7 + 7 + 7 = 21\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == flights.length</code></li>\n",
    "\t<li><code>n == flights[i].length</code></li>\n",
    "\t<li><code>n == days.length</code></li>\n",
    "\t<li><code>k == days[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n, k &lt;= 100</code></li>\n",
    "\t<li><code>flights[i][j]</code>&nbsp;不是&nbsp;<code>0</code>&nbsp;就是&nbsp;<code>1</code></li>\n",
    "\t<li><code>0 &lt;= days[i] &lt;= 7</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-vacation-days](https://leetcode.cn/problems/maximum-vacation-days/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-vacation-days](https://leetcode.cn/problems/maximum-vacation-days/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,1],[1,0,1],[1,1,0]]\\n[[1,3,1],[6,0,3],[3,3,3]]', '[[0,0,0],[0,0,0],[0,0,0]]\\n[[1,1,1],[7,7,7],[7,7,7]]', '[[0,1,1],[1,0,1],[1,1,0]]\\n[[7,0,0],[0,7,0],[0,0,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        #无脑dp \n",
    "        # dp[k][n] = max(dp[k-1][能到的city])+days[k][n]\n",
    "        k = len(days[0])\n",
    "        n = len(flights)\n",
    "        dp = [[-1]*n for _ in range(k+1)]\n",
    "        dp[-1][0] = 0\n",
    "        for d in range(k):\n",
    "            for i in range(n):\n",
    "                if dp[d-1][i] >= 0 :\n",
    "                    dp[d][i] =  dp[d-1][i]  +days[i][d]\n",
    "                for j in range(n):\n",
    "                    if flights[j][i] == 0 or dp[d-1][j]<0:continue\n",
    "                    dp[d][i] = max(dp[d][i] ,dp[d-1][j]+days[i][d] )\n",
    "        \n",
    "        return max(dp[-2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        n = len(days)\n",
    "        dp = [0]+[-inf]*(n-1)\n",
    "        for k in range(len(days[0])):\n",
    "            new = [-inf]*n\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i==j or flights[i][j]:\n",
    "                        new[j] = max(new[j],dp[i]+days[j][k])\n",
    "            dp = new\n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights, days):\n",
    "        if len(days) == 0 or len(flights) == 0:\n",
    "            return 0\n",
    "        dp = [[0 for _ in range(len(days[0]) + 1)] for _ in range(len(days))]\n",
    "        for week in range(len(days[0]) - 1, -1, -1):\n",
    "            for cur_city in range(len(days)):\n",
    "                for dest_city in range(len(days)):\n",
    "                    if flights[cur_city][dest_city] == 1 or dest_city == cur_city:\n",
    "                        dp[cur_city][week] = max(days[dest_city][week] + dp[dest_city][week + 1], dp[cur_city][week])\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights, days):\n",
    "        if len(days) == 0 or len(flights) == 0:\n",
    "            return 0\n",
    "        dp = [[0 for _ in range(len(days[0]) + 1)] for _ in range(len(days))]\n",
    "        for week in range(len(days[0]) - 1, -1, -1):\n",
    "            for cur_city in range(len(days)):\n",
    "                dp[cur_city][week] = days[cur_city][week] + dp[cur_city][week + 1]\n",
    "                for dest_city in range(len(days)):\n",
    "                    if flights[cur_city][dest_city] == 1:\n",
    "                        dp[cur_city][week] = max(days[dest_city][week] + dp[dest_city][week + 1], dp[cur_city][week])\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        N = len(flights)\n",
    "        K = len(days[0])\n",
    "        dp = [[(0, 0)] * N]\n",
    "        for i in range(K):\n",
    "            dp.append([])\n",
    "            for j in range(N):\n",
    "                for k in range(len(dp[i])):\n",
    "                    before = dp[i][k][1]\n",
    "                    beforeD = dp[i][k][0]\n",
    "                    if before == j or flights[before][j] == 1:\n",
    "                        dp[i+1].append((beforeD + days[j][i], j))\n",
    "                        break\n",
    "                    # if i == 1 and j == 1 and k == 0:\n",
    "                    #     return dp\n",
    "            dp[i+1].sort(reverse=True)\n",
    "            # if i == 1:\n",
    "            #     return dp\n",
    "        return dp[K][0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        N = len(flights)\n",
    "        K = len(days[0])\n",
    "        dp = [[(0, 0)] * N]\n",
    "        for i in range(K):\n",
    "            dp.append([])\n",
    "            for j in range(N):\n",
    "                for k in range(len(dp[i])):\n",
    "                    before = dp[i][k][1]\n",
    "                    beforeD = dp[i][k][0]\n",
    "                    if before == j or flights[before][j] == 1:\n",
    "                        dp[i+1].append((beforeD + days[j][i], j))\n",
    "                        break\n",
    "            dp[i+1].sort(reverse=True)\n",
    "        return dp[K][0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        N = len(flights)\n",
    "        K = len(days[0])\n",
    "        dp = [[(0, 0)] * N]\n",
    "        result = 0\n",
    "        for i in range(K):\n",
    "            dp.append([])\n",
    "            for j in range(N):\n",
    "                sign = 0\n",
    "                day = 0\n",
    "                for k in range(len(dp[i])):\n",
    "                    before = dp[i][k][1]\n",
    "                    beforeD = dp[i][k][0]\n",
    "                    if before == j or flights[before][j] == 1:\n",
    "                        day = max(beforeD + days[j][i], day)\n",
    "                        sign = 1\n",
    "                if sign == 1:\n",
    "                    dp[i+1].append((day, j))\n",
    "                    result = max(result, day)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        N = len(flights)\n",
    "        K = len(days[0])\n",
    "        dp = [[(0, 0)] * N]\n",
    "        result = 0\n",
    "        for i in range(K):\n",
    "            dp.append([])\n",
    "            for j in range(N):\n",
    "                sign = 0\n",
    "                day = 0\n",
    "                for k in range(len(dp[i])):\n",
    "                    before = dp[i][k][1]\n",
    "                    beforeD = dp[i][k][0]\n",
    "                    if before == j or flights[before][j] == 1:\n",
    "                        day = max(beforeD + days[j][i], day)\n",
    "                        sign = 1\n",
    "                if sign == 1:\n",
    "                    dp[i+1].append((day, j))\n",
    "                    result = max(result, day)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        N = len(flights)\n",
    "        K = len(days[0])\n",
    "        first = SortedList([(0, 0)] * N)\n",
    "        dp = [first]\n",
    "        for i in range(K):\n",
    "            dp.append(SortedList([]))\n",
    "            for j in range(N):\n",
    "                for k in range(len(dp[i])-1, -1, -1):\n",
    "                    before = dp[i][k][1]\n",
    "                    beforeD = dp[i][k][0]\n",
    "                    if before == j or flights[before][j] == 1:\n",
    "                        dp[i+1].add((beforeD + days[j][i], j))\n",
    "                        break\n",
    "        return dp[K][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        N = len(flights)\n",
    "        K = len(days[0])\n",
    "        dp = [SortedList([(0, 0)] * N)]\n",
    "        for i in range(K):\n",
    "            dp.append(SortedList())\n",
    "            for j in range(N):\n",
    "                for k in range(len(dp[i])-1, -1, -1):\n",
    "                    before = dp[i][k][1]\n",
    "                    beforeD = dp[i][k][0]\n",
    "                    if before == j or flights[before][j] == 1:\n",
    "                        dp[i+1].add((beforeD + days[j][i], j))\n",
    "                        break\n",
    "        return dp[K][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]\n",
    "        :param flights:\n",
    "        :param days:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def xxx():\n",
    "            return -math.inf\n",
    "        dp = defaultdict(xxx)\n",
    "        edge = defaultdict(list)\n",
    "        edge2 = defaultdict(list)\n",
    "        for k,v in enumerate(flights):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if v2 == 1:\n",
    "                    edge[k2].append(k)\n",
    "                    edge2[k].append(k2)\n",
    "\n",
    "        for i in range(len(days[0])):\n",
    "            if i == 0:\n",
    "                for j in range(len(flights)):\n",
    "                    if j in edge2[0]:\n",
    "                        dp[(j, i)] = days[j][i]\n",
    "                dp[(0, 0)] = days[0][0]\n",
    "\n",
    "            else:\n",
    "                for j in range(len(flights)):\n",
    "                    for x in edge[j]:\n",
    "                        prev1 = dp[(x, i-1)]\n",
    "\n",
    "                        dp[(j, i)] = max(prev1 + days[j][i], dp[(j, i)])\n",
    "                    dp[(j, i)] = max(dp[(j, i)], dp[(j, i-1)] + days[j][i] )\n",
    "        ret = -math.inf\n",
    "        for i in range(len(flights)):\n",
    "            ret = max(ret, dp[i, len(days[0])-1])\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]\n",
    "        :param flights:\n",
    "        :param days:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        tl = len(flights)\n",
    "        def xxx():\n",
    "            return -math.inf\n",
    "        dp = defaultdict(xxx)\n",
    "        edge = defaultdict(list)\n",
    "        edge2 = defaultdict(list)\n",
    "        for k,v in enumerate(flights):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if v2 == 1:\n",
    "                    edge[k2].append(k)\n",
    "                    edge2[k].append(k2)\n",
    "\n",
    "        for i in range(len(days[0])):\n",
    "            if i == 0:\n",
    "                for j in range(len(flights)):\n",
    "                    if j in edge2[0]:\n",
    "                        dp[(j, i)] = days[j][i]\n",
    "                dp[(0, 0)] = days[0][0]\n",
    "\n",
    "            else:\n",
    "                for j in range(len(flights)):\n",
    "                    for x in edge[j]:\n",
    "                        prev1 = dp[(x, i-1)]\n",
    "\n",
    "                        dp[(j, i)] = max(prev1 + days[j][i], dp[(j, i)])\n",
    "                    dp[(j, i)] = max(dp[(j, i)], dp[(j, i-1)] + days[j][i] )\n",
    "        ret = -math.inf\n",
    "        for i in range(len(flights)):\n",
    "            ret = max(ret, dp[i, len(days[0])-1])\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        city_num,week_num = len(flights), len(days[0])\n",
    "        @cache\n",
    "        def dfs(cur_city_index, week_no):\n",
    "            if week_no == week_num:\n",
    "                return 0\n",
    "            maxvac = 0\n",
    "            for nxt in range(city_num):\n",
    "                if flights[cur_city_index][nxt]==1 or nxt == cur_city_index:\n",
    "                    return_vac = days[nxt][week_no] + dfs(nxt,week_no + 1)\n",
    "                    \n",
    "                    maxvac = max(return_vac, maxvac)\n",
    "            return maxvac\n",
    "        return dfs(0,0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    记忆化搜索\n",
    "    在week周（从0开始）从start开始，要飞到nxt城市（只要是能飞或者不飞）的最长假期\n",
    "    从start开始飞一次可能有多种选择，要从多个选择中选一个最大的\n",
    "    '''\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        n = len(flights)\n",
    "        k = len(days[0])\n",
    "\n",
    "        @cache\n",
    "        def helper(start, week):\n",
    "            nonlocal n, k\n",
    "            if week == k:\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for nxt in range(n):\n",
    "                if flights[start][nxt] or start == nxt:\n",
    "                    time = days[nxt][week] + helper(nxt, week + 1)\n",
    "                    res = max(res, time)\n",
    "            return res\n",
    "        \n",
    "        return helper(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def back(day,city):\n",
    "            if day == len(days[0]):return 0\n",
    "            res = back(day+1,city)+days[city][day]\n",
    "            for i in range(len(flights)):\n",
    "                if not flights[city][i]:continue\n",
    "                res = max(res,back(day+1,i)+days[i][day])\n",
    "            return res\n",
    "        return back(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        n,k = len(flights),len(days[0])\n",
    "        d = defaultdict(list)\n",
    "        for i,row in enumerate(flights):\n",
    "            for j,x in enumerate(row):\n",
    "                if x == 1:\n",
    "                    d[i].append(j)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if i == k or c == n:\n",
    "                return 0\n",
    "            #第i周留在当前城市\n",
    "            ans = days[c][i] + dfs(i + 1,c)\n",
    "            for nc in d[c]:\n",
    "                ans = max(ans,dfs(i + 1,nc) + days[nc][i])\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        n,k = len(flights),len(days[0])\n",
    "        d = defaultdict(list)\n",
    "        for i,row in enumerate(flights):\n",
    "            for j,x in enumerate(row):\n",
    "                if x == 1:\n",
    "                    d[i].append(j)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,c):\n",
    "            if i == k:\n",
    "                return 0\n",
    "            #第i周留在当前城市\n",
    "            ans = days[c][i] + dfs(i + 1,c)\n",
    "            for nc in d[c]:\n",
    "                ans = max(ans,dfs(i + 1,nc) + days[nc][i])\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVacationDays(self, flights: List[List[int]], days: List[List[int]]) -> int:\n",
    "        n = len(flights)\n",
    "        k = len(days[0])\n",
    "\n",
    "        @cache\n",
    "        def helper(start, week):\n",
    "            nonlocal n, k\n",
    "            if week == k:\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            for nxt in range(n):\n",
    "                if flights[start][nxt] or start == nxt:\n",
    "                    time = days[nxt][week] + helper(nxt, week + 1)\n",
    "                    res = max(res, time)\n",
    "            return res\n",
    "        \n",
    "        return helper(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
